#include <iostream>
#include <string.h>
#include <vector>


using namespace std;



typedef enum{Link, Thread} NodeTag;

class TreeNode
{
private:
    char data;              //值
    TreeNode* leftChild;    //左孩子
    TreeNode* rightChild;   //右孩子
    NodeTag lTag, rTag;     //线索Tag

    friend class MyTree;    //树类

    friend class MyStack;//栈类
    friend class listNode;

    
public:
    TreeNode(char, TreeNode*, TreeNode*, NodeTag, NodeTag);
    ~TreeNode();

    void printNode();
    
};

class MyTree
{
private:
     TreeNode* root;        //根指针
     bool isThread;         //线索二叉树标志

     const char* ptr;//初始化树用的前序表达
     TreeNode* prevnode;//新增线索化关键前指

     TreeNode* creatbitree();
     TreeNode * copy(TreeNode *);
     int leafcount(TreeNode *);
     int heightcount(TreeNode *);
     void destroyTree(TreeNode* rt);

public:
    MyTree();               //无参构造
    MyTree(const char[]);   //构造函数
    MyTree(const MyTree&);  //拷贝函数
    ~MyTree();              //析构函数

    void preOrderTraverse();    //前序遍历
    void inOrderTraverse();     //中序遍历
    void postOrderTraverse();   //后序遍历
    int countLeaf();            //叶结点计数
    int countHeight();          //计算树的深度
    bool isThreadedTree();      //判断是否为线索二叉树
    bool inOrderThreading();    //线索化
    TreeNode& locateNode(const char&);  //结点定位
    TreeNode& preNode(const TreeNode&); //获取前驱结点
    TreeNode& nextNode(const TreeNode&);//获取后继结点

};


class HuffmanTree
{
private:
    //添加必要的数据成员
    int n;                    // 叶子数量
    int *weights;             // 初始权值数组，长度 n
    std::vector<std::string> codes; // 存放每个叶子(输入节点)的编码，codes[i] 对应 weights[i]
    // 内部节点数组将存在 cpp 实现中（使用动态结构）
  
public:
    HuffmanTree(const int&,const int[]);    //构造函数
    ~HuffmanTree();     //析构函数

    //输出哈夫曼编码
    //格式为：每行输出一个节点，节点排序递减
    //节点1值：编码
    //节点2值：编码
    //....
    //cpp中未给出该函数，遵守输出格式规范
    void printHuffmanCodes();   

 
};


//栈
class MyStack;

class listNode{
    friend class MyStack;
    friend class MyTree;
private:
    listNode* next;
    TreeNode * tree;//树的节点
public:
    listNode();
    listNode(TreeNode * nodeData, listNode* succ = NULL);
};

class MyStack
{
private:
    listNode* topNode;
    int stackSize;


public:
    MyStack();
    ~MyStack();

    bool push(TreeNode*);//存一个节点进去
    bool pop(TreeNode* &);//弹栈，弹出的节点存参数里
    bool getTop(TreeNode * &);//取但不弹
    //void printStack();

    bool isEmpty();//栈是否空

    friend class MyTree;
    friend class TreeNode;
    
};
